package com.cat.dataStructure02;

import java.util.Arrays;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/find-the-kth-smallest-sum-of-a-matrix-with-sorted-rows/
 * @create 2025/10/28 20:45
 * @since JDK17
 */

public class Solution77 {
    public int kthSmallest(int[][] mat, int k) {
        int[] a = new int[]{0};
        for (var row : mat) {
            int[] b = new int[a.length * row.length];
            int i = 0;
            for (int x : a) {
                for (int y : row) {
                    b[i++] = x + y;
                }
            }
            Arrays.sort(b);
            if (b.length > k) {
                b = Arrays.copyOfRange(b, 0, k);
            }
            a = b;
        }

        return a[k - 1];
    }
}
